Gaussian elimination method

求解矩阵的高斯消元法

高斯消元法是求解矩阵最基础的一种算法，具有泛化性强的优点。

消元过程

对于方程组$Ax=b$（其中A为n阶方阵）可由n-1个消元过程和n-1个回代过程完成求解

$$\begin{cases} a_{11}x_1+a_{12}x_2+a_{13}x_3+\cdots+a_{1n}x_n=&b_1 \\\vdots\\ a_{n1}x_1+a_{n2}x_2+a_{n3}x_3+\cdots+a_{nn}x_n=&b_n& \end{cases} \\ \begin{pmatrix} a_{11}&a_{12}&a_{13}&\dots&a_{1n}\\ a_{21}&a_{22}&a_{23}&\dots&a_{2n}\\ \vdots&&&&\vdots\\ a_{n1}&a_{n2}&a_{n3}&\dots&a_{nn} \end{pmatrix} \begin{pmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{pmatrix}= \begin{pmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{pmatrix}$$

1. 矩阵的消元过程(在矩阵有解的情况下)

   • 第一步消元

   $a_{ij}^{(1)}=a_{ij}^{(0)}-\frac{a_{i1}^{(0)}} {a_{11}^{(0)}}a_{1j}^{(0)}=a_{ij}^{(0)}-l_{i1}^{(0)}a_{1j}^{(0)} ,\quad i=2,3,\dots,n;j=2,3,\dots,n$

   $b_{i}^{(1)}=b_{i}^{(0)}-\frac{a_{i1}^{(0)}} {a_{11}^{(0)}}b_{1}^{(0)}=b_{i}^{(0)}-l_{i1}^{(0)}b_{1}^{(0)} ,\quad i=2,3,\dots,n$

   $l_{i1}\triangleq \frac {a_{i1}^{(0)}} {a_{11}^{(0)}},\quad i=2,3,\dots,n$

   • 第k步消元

     $a_{ij}^{(k)}=a_{ij}^{(k-1)}-\frac{a_{ik}^{(k-1)}} {a_{kk}^{(k-1)}}a_{kj}^{(k-1)}=a_{ij}^{(k-1)}-l_{ik}^{(k-1)}a_{kj}^{(k-1)} ,\quad i=k+1,k+2,\dots,n;j=k=1,k+2,\dots,n$

     $b_{i}^{(k)}=b_{i}^{(k-1)}-\frac{a_{ik}^{(k-1)}} {a_{kk}^{(k-1)}}b_{k}^{(k-1)}=b_{i}^{(k-1)}-l_{ik}^{(k-1)}b_{k}^{(k-1)} ,\quad i=k+1,k+2,\dots,n$

     $l_{ik}\triangleq \frac {a_{ik}^{(k-1)}} {a_{kk}^{(k-1)}},\quad i=k+1,k+2,\dots,n$

   • 消元完成后

     $$A^{(n-1)}= \begin{pmatrix} a_{11}^{(0)}&a_{12}^{(0)}&a_{13}^{(0)}&\cdots&\cdots&a_{1n}^{(0)}\\ &a_{22}^{(1)}&a_{23}^{(1)}&\cdots&\cdots&a_{2n}^{(1)}\\ &&\ddots\\ &&&a_{kk}^{(k-1)}&\cdots&a_{kn}^{(k-1)}\\ &&&&\ddots&\vdots\\ &&&&&a_{nn}^{(n-1)} \end{pmatrix},\quad b^{(n-1)}= \begin{pmatrix} b_{1}^{(0)}\\ b_{2}^{(1)}\\ \vdots\\ b_{k}^{(k-1)}\\ \vdots\\ b_{n}^{(n-1)} \end{pmatrix}$$

1. 回代的过程 $$\left\{ \begin{array} x_n=\frac{b_n^{n-1}}{a_{nn}^{(n-1)}}\\ x_k=\frac{ {b_k}^{(k-1)-\sum_{j=k+1}^n(a_{kj}^{(k-1)}x_j)} } {a_{kk}^{(k-1)} },\quad k=n-1,n-2,\dots,2,1. \end{array} \right.$$

算法的分析

• [ ] 在消元的过程中，计算$l_{ik}\triangleq \frac {a_{ik}^{(k-1)}} {a_{kk}^{(k-1)}},\quad i=k+1,k+2,\dots,n$时共有n-k个除法，而计算$a_{ij}^{(k)}=a_{ij}^{(k-1)}-l_{ik}^{(k-1)}a_{kj}^{(k-1)} ,\quad i=k+1,k+2,\dots,n;j=k=1,k+2,\dots,n$时有$(n-k)^2$个乘法，计算$b_{i}^{(k)}=b_{i}^{(k-1)}-l_{ik}^{(k-1)}b_{k}^{(k-1)} ,\quad i=k+1,k+2,\dots,n$时也有n-k个乘法，消元共进行了n-1步，即$k=1,2,\dots,n-1$.

• [ ] ==所以在消元过程中乘除法的运算量为==

  $$N_1=\sum_{k=1}^{n-1}((n-k)^2+2(n-k))=n^3/3+n^2/2-5n/6.$$

• [ ] ==回代过程中乘除法的运算量为==

  $$N_2=\sum_{k=1}^{n-1}(n-k)+n=n^2/2+n/2.$$

  • [ ] ==所以高斯消元法解n阶矩阵的总乘除法运算量为==

    $N=N_1+N_2=n^3/3+n^2-n/3$

高斯消元法的程序实现

我们可以封装一个Matrix类如下

class Matrix
{
    public int row = 0;
    public int column = 0;           
    private float[,] matrix;
    public Matrix(int row, int column)
    {
        this.row = row;
        this.column = column;
        matrix = new float[row, column];
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < column; j++)
            {
                string mid = Console.ReadLine();
                var rows = mid.Split(' ');
                foreach (var item in rows)
                {
                    matrix[i, j++] = float.Parse(item);
                }

            }

        }
    }
    public void DisPlay()
    {                                         
            for (int i = 0; i < this.row; i++)
            {
                for (int j = 0; j < this.column; j++)
                {
                    Console.Write(matrix[i, j] + " ");
                }
                Console.WriteLine("\r");
            }                
    }

    public void Simplize()
    {
        for (int i = 0; i < this.row ; i++)
        {
            if (matrix[i, i] != 0)
            {
                for (int k = i + 1; k < row ; k++)
                {
                    matrix[k, i] = matrix[k, i] / matrix[i, i];
                }
            }//这里将消元的中间量存在被消元的位置，因为运算后，这些位置的值为零
            for (int j = i + 1; j < row; j++)
            {
                for (int k = i + 1; k < column; k++)
                {
                    matrix[j, k] = matrix[j, k] - matrix[j, i] * matrix[i, k];
                }
            }
        }
    }
}

当我们输入

$$\begin{pmatrix} 1&2&1&0\\ 2&2&3&3\\ -1&-3&0&2 \end{pmatrix}$$

时，并调用Simplize和DisPlay方法，将得到结果如下

事实上，这是一个矩阵的LU分解，LU分解在矩阵的研究中有着重要的地位，是十分常用的一个分解方法。

高斯消元法的缺点

• 高斯消元法的运算量较大
• 高斯消元法的顺利进行要求矩阵满足某些要求